package com.markus.code.动态规划.硬币问题;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/26 9:02
 * todo: 硬币问题
 */
public class Coin_lcci {
    public int waysToChange1(int n) {
        int coins[] = {25, 10, 5, 1};
        return process1(coins, coins.length - 1, n);
//        return process(coins,n);
    }

    /**
     * coins : 金币面值
     * index : 当前索引
     * rest  : 剩余值
     * 递归的意义就是：f(i,rest)表示0~i位置上的币值，凑成rest金额的种类数
     * 递归下去就是穷举：选0张-->f(i-1,rest)
     * 选1张-->f(i-1,rest-coins[i])
     * ...
     * 知道选到n张-->f(i-1,0)
     */
    private int process1(int[] coins, int index, int rest) {
        if (index < 0) {
            return rest == 0 ? 1 : 0;
        }
        if (rest == 0) {
            return 1;
        }
        //选择不要当前硬币
        int typeNo = process1(coins, index - 1, rest);
        int typeYes = 0;
        for (int i = 1; rest - i * coins[index] >= 0; i++) {
            typeYes += process1(coins, index - 1, rest - i * coins[index]);
        }
        return (typeNo + typeYes) % 1000000007;
    }

    public int waysToChange(int n) {
        int []coins = {25,10,5,1};
        int[][] dp = getDp(coins, n);
        return dp[coins.length-1][n];
    }
    private int[][] getDp(int[] coins, int money) {
        int[][] dp = new int[coins.length][money + 1];
        //填基本数据
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i * coins[0] <= money; i++) {
            dp[0][i * coins[0]] = 1;
        }
        //填普通数据
        for (int i=1;i<coins.length;i++){
            for (int j=1;j<=money;j++){
                //首先，先得出不选择当前币值的情况
                dp[i][j] = dp[i-1][j];
                //其次，再得出选择当前币值的枚举情况
                dp[i][j] += j-coins[i]>=0?dp[i][j-coins[i]]:0;
                dp[i][j] %= 1000000007;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        Coin_lcci demo = new Coin_lcci();
        System.out.println(demo.waysToChange(900750));
    }
}
